/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-11-15
 * Time: 10:20
 */
import java.util.Arrays;

public class GraphColoring {
    private int minColors; // 最少需要的颜色数
    private int[] bestColoring; // 最优着色方案（记录每个顶点的颜色）

    public int[] solveGraphColoring(int[][] graph) {
        int n = graph.length; // 顶点数量
        if (n == 0) return new int[0];

        minColors = n; // 最坏情况：每个顶点一种颜色
        int[] currentColoring = new int[n]; // 当前着色方案（初始为0，未着色）
        Arrays.fill(currentColoring, 0);

        // 从第0个顶点开始回溯，尝试用1种颜色、2种颜色...直到找到可行方案
        backtrack(graph, 0, currentColoring, 1);

        return bestColoring;
    }

    // 回溯函数：给第v个顶点着色，currentColors是当前使用的颜色数
    private void backtrack(int[][] graph, int v, int[] currentColoring, int currentColors) {
        int n = graph.length;

        // 终止条件：所有顶点都着色完成
        if (v == n) {
            // 更新最小颜色数和最优方案
            if (currentColors < minColors) {
                minColors = currentColors;
                bestColoring = Arrays.copyOf(currentColoring, n);
            }
            return;
        }

        // 尝试为当前顶点v分配颜色（从1到currentColors+1，最多比当前颜色数多1）
        for (int color = 1; color <= currentColors + 1; color++) {
            // 检查颜色是否与相邻顶点冲突
            if (isValidColor(graph, v, currentColoring, color)) {
                currentColoring[v] = color; // 分配颜色

                // 确定新的颜色数（如果用了新颜色，currentColors+1）
                int newColors = (color > currentColors) ? currentColors + 1 : currentColors;

                // 剪枝：如果当前颜色数已超过已知的最小颜色数，无需继续
                if (newColors < minColors) {
                    backtrack(graph, v + 1, currentColoring, newColors);
                }

                currentColoring[v] = 0; // 回溯：撤销颜色分配
            }
        }
    }

    // 检查顶点v分配颜色color是否合法（与相邻顶点颜色不同）
    private boolean isValidColor(int[][] graph, int v, int[] currentColoring, int color) {
        for (int u = 0; u < graph.length; u++) {
            // 如果u和v相邻，且u已着色，且颜色相同，则冲突
            if (graph[v][u] == 1 && currentColoring[u] == color) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        // 示例图：邻接矩阵表示（graph[i][j]=1表示顶点i和j相邻）
        // 顶点0-3的图：0-1, 0-2, 1-2, 1-3, 2-3 相邻
        int[][] graph = {
                {0, 1, 1, 0}, // 顶点0：与1、2相邻
                {1, 0, 1, 1}, // 顶点1：与0、2、3相邻
                {1, 1, 0, 1}, // 顶点2：与0、1、3相邻
                {0, 1, 1, 0}  // 顶点3：与1、2相邻
        };

        GraphColoring solver = new GraphColoring();
        int[] coloring = solver.solveGraphColoring(graph);

        System.out.println("最少需要的颜色数：" + solver.minColors); // 输出 3
        System.out.println("每个顶点的颜色（索引对应顶点）：" + Arrays.toString(coloring));
        // 示例输出：[1, 2, 3, 1]（颜色1、2、3，相邻顶点颜色不同）
    }
}
